#include <cstdio>

#define MAX_SIZE 1501
#define MAX_FACTORS 3


template <typename N>
inline N & min (N &a, N &b)
{
	return a > b ? b : a;
}


template <typename N>
inline N & min (N &a, N &b, N &c)
{
	return min (min (a, b), c);
}


template <typename N>
inline N & min (N v[MAX_FACTORS])
{
	N &r = min (v[0], v[1], v[2]);
	return min (v[0], v[1], v[2]);
}


template <typename N>
inline int min_index (N v[MAX_FACTORS])
{
	return &(min (v)) - v;
}


inline int ugly_number (int n)
{
	static int
		un[MAX_SIZE] = {1},
		*uf[MAX_FACTORS] = {un, un, un},
		*last = un;
	static const int factor[MAX_FACTORS] = {2, 3, 5};
	int index, temp[MAX_FACTORS];

	int &r = un[n - 1];

	while (!r)
	{
		temp[0] = *uf[0] * factor[0];
		temp[1] = *uf[1] * factor[1];
		temp[2] = *uf[2] * factor[2];
		index = min_index (temp);
		if (*last != temp[index])
		{
			++last;
		}
		*last = temp[index];
		++uf[index];
	}

	return r;
}


int main ()
{
	printf("The 1500'th ugly number is %d.\n", ugly_number (1500));
	return 0;
}